#include "integer.h"
#include "converter.h"
#include "exceptions.h"
#include "global_variables.h"

static bool is_negative(const string &s1) {
  if (s1.length() > 0 && s1[0] == '-')
    return true;
  else
    return false;
} // is negative

static void string_abs(string &s) {
  if (is_negative(s) == true)
    s.erase(0, 1);
} // string_abs

static bool is_s1_smaller_than_s2(const string &s1, const string &s2) {
  if (is_negative(s1) == true && is_negative(s2) == false)
     return true;
  else if (is_negative(s1) == false && is_negative(s2) == true)
    return false;

  // both s1 and s2 are negative or positive
  const size_t len1 = s1.length();
  if (s2.length() > len1)
    return true;
  else if (s2.length() == len1) {
    size_t i = 0;
    while (i < len1 && s1[i] == s2[i])
      ++i;

    if (i == len1)
      return false; // s1 is equal to s2

    if (is_negative(s1) == true)
      return !(s1[i] < s2[i]); // both s1 & s2 are negative
    else
      return (s1[i] < s2[i]);

  } else
    return false;
} // is_s1_smaller_than_s2

static bool is_number(const string &s) {
  bool negative = false;

  for (size_t i = 0; i < s.length(); ++i) {
    if (s[i] < '0' || s[i] > '9') {
       if (s[i] == '-' && negative == false) // just one '-' is allowed
         negative = true;
       else
         return false;

    } // if
  } // for i

  return true;
} // is_number

// this one is more efficient than decimal_to_binary
static string int_to_bin(unsigned int input) {
  string result;

  unsigned int size = sizeof(input) * 8; // each byte needs 8 bits

  // finds out how long the input is in binary form
  for (size_t i = size - 1; i > 0; --i) {
    if (((input >> i) & 01) == 00)
      --size;
    else
      break;

  } // for i

  result = (char) ((01 & input) + '0'); // the lowest bit

  for (size_t i = 1; i < size; ++i)
    result.insert(0, 1, (char) ((01 & (input >> i)) + '0'));

  return result;
} // int_to_bin

////

const string &integer::to_string() const {
  return s;
} // integer::to_string

void integer::set(const string &s1) {
  if (is_number(s) == false)
    throw operation_not_allowed_exception("Not a number!");
  else
    s = s1;
} // integer::set

size_t integer::len() const {
  return s.length();
} // integer::len

const string &integer::get_rest() const {
  return rest;
} // integer::get_rest

integer &integer::operator=(const integer &i1) {
  if (&i1 == this)
    return (*this);

  s = i1.s;
  rest = i1.rest;
  return (*this);
} // integer::operator=

integer &integer::operator=(const string &s1) {
  if (is_number(s1) == false)
    throw operation_not_allowed_exception("Not a number!");
  else {
    s = s1;
    rest = "0";
    return (*this);
  } // else
} // integer::operator=

integer &integer::operator=(int i) {
  converter::to_string(i, s);
  rest = "0";
  return (*this);
} // integer::operator=

bool integer::operator==(const integer &i1) const {
  if (i1.s == s)
    return true;
  else
    return false;
} // integer::operator==

bool integer::operator==(const string &s1) const {
  if (s1 == s)
    return true;
  else
    return false;
} // integer::operator==

bool integer::operator<(const integer &i1) const {
  return is_s1_smaller_than_s2(s, i1.s);
} // integer::operator<

bool integer::operator<=(const integer &i1) const {
  return ((*this) < i1 || (*this) == i1);
} // integer::operator<=

bool integer::operator<(const string &s) const {
  const integer i1(s);
  return (*this < i1);
} // integer::operator<

bool integer::operator>(const integer &i1) const {
  return (i1 < *this);
} // integer::operator>

bool integer::operator>=(const integer &i1) const {
  return ((*this) > i1 || (*this) == i1);
} // integer::operator>=

bool integer::operator>(const string &s) const {
  const integer i1(s);
  return (*this > i1);
} // integer::operator>

integer integer::operator+(const integer &i1) const {
  // problem: you want to add a to b
  // solution: there is no special idea used in this function, it is based on algorithm that you
  //           learn in the school to add two numbers.
  //           a and b could be theoretically endlessly long.
  //           the longer a and b are, the more time it takes to calculate their addition.

  short hlp1 = 0; // is used in adding and subtracting operations
  short rest = 0; // is used in adding operations
  short digit_of_str1;
  short digit_of_str2;

  size_t i;
  size_t len1 = s.length();
  size_t len2 = i1.len();
  size_t pos; // holds position in cases like (2 - 8), which need a decrementation from previous digits

  integer hlp2; // the object that will be returned

  string str1; // holds the bigger number
  string str2; // holds the smaller number

  char sign = '\0';

  if ((is_negative(s) == true && is_negative(i1.s) == true) ||
      (is_negative(s) == false && is_negative(i1.s) == false)) {

    if (is_negative(s) == true)
      sign = '-';

    if (is_s1_smaller_than_s2(s, i1.s)) {
      str1 = i1.s;
      str2 = s;
    } else {
      str1 = s;
      str2 = i1.s;
    } // else

    string_abs(str1);
    string_abs(str2);

    len1 = str1.length() - 1; // bigger number
    len2 = str2.length() - 1; // smaller number

    while (len1 != string::npos) {
      digit_of_str1 = (str1[len1] - 48);

      if (len2 != string::npos) {
        digit_of_str2 = (str2[len2] - 48);
        --len2;
      } else
        digit_of_str2 = 0;

      hlp1 = digit_of_str1 + digit_of_str2 + rest;

      if (hlp1 >= 10) {
        rest = hlp1 / 10;
        hlp1 %= 10;
      } else
        rest = 0;

      hlp2.s.insert(0, 1, char(hlp1 + 48));

      --len1;
    } // while

    if (rest != 0)
      hlp2.s.insert(0, 1, char(rest + 48));

    // removes zero digits before any valuable digit
    i = 0;
    while (hlp2.s.length() > 1 && hlp2.s[i] == '0')
      ++i;

    hlp2.s.erase(0, i);

    if (sign == '-')
      hlp2.s.insert(0 ,1, sign);

    return hlp2;

  } else if (is_negative(s) == true && is_negative(i1.s) == false) {
    const string tmp(s, 1); // removes the minus sign

    if (is_s1_smaller_than_s2(i1.s, tmp)) {
      sign = '-';
      str1 = tmp;
      str2 = i1.s;
    } else {
      str1 = i1.s;
      str2 = tmp;
    } // else

  } else if (is_negative(s) == false && is_negative(i1.s)) {
    const string tmp(i1.s, 1); // removes the minus sign

    if (is_s1_smaller_than_s2(s, tmp)) {
      sign = '-';
      str1 = tmp;
      str2 = s;
    } else {
      str1 = s;
      str2 = tmp;
    } // else
  } // else

  len1 = str1.length() - 1; // bigger number
  len2 = str2.length() - 1; // smaller number

  while (len1 != string::npos) {
    digit_of_str1 = (str1[len1] - 48);

    if (len2 != string::npos) {
      digit_of_str2 = (str2[len2] - 48);
      --len2;
    } else
      digit_of_str2 = 0;

    if (digit_of_str1 < digit_of_str2) {
      pos = len1;
      i = pos - 1;

      while (str1[i] == '0')
        --i;

      str1[i] = str1[i] - 1;
      ++i;

      while (i < pos) {
        str1[i] = str1[i] + 9;
        ++i;
      } // while

      hlp1 = (str1[i] - 48) + 10 - digit_of_str2;
    } else
      hlp1 = digit_of_str1 - digit_of_str2;

    hlp2.s.insert(0, 1, char(hlp1 + 48));

    --len1;
  } // while

  // removes zero digits before any valuable digit
  i = 0;
  while (hlp2.s.length() > 1 && hlp2.s[i] == '0')
    ++i;

  // makes sure that when the result is 0, one zero stays intact and the rest will be removed
  if (i < hlp2.s.length())
    hlp2.s.erase(0, i);
  else
    hlp2.s = "0";

  if (sign == '-')
    hlp2.s.insert(0, 1, sign);

  return hlp2;
} // integer::operator+

integer integer::operator-(const integer &i1) const {
  // see operator+

  integer tmp;

  if (i1.s[0] == '-')
    tmp.s.assign(i1.s, 1, i1.s.length() - 1);
  else {
    tmp.s = '-';
    tmp.s += i1.s;
  } // else

  return (*this) + tmp;
} // integer::operator-

integer integer::operator*(const integer &i1) const {
  // problem: you want to multiply p = 123 with q = 764883
  // solution: (1st solution): add 123 to itself 764883 times
  //           this solution is pretty slow, that is why we do the following
  //           (2nd solution):
  //           add 123 to itself 3 times and save it to p, and decrement q by 3
  //           after that the problem will be
  //           problem: multiply p with q = 764880
  //           solution: remove the zero from the right side of q and add it to p
  //           so that new p will be equal to old p * 10 (string operations and not mathematical)
  //           and new q will be equal to q / 10 (string operations and not mathematical)
  //           continue this process until q is 0

  integer counter(i1.s); // is used to make the multiplication faster
  string_abs(counter.s);
  string *tmp1 = &counter.s;

  static const integer sample("1");
  integer result;
  integer big_part = get_abs(); // actually (*this).get_abs(), is used to make the multiplication faster
  char sign;

  if (is_negative(i1.s) && is_negative(s))
    sign = '\0';
  else if (is_negative(i1.s) == false && is_negative(s) == false)
    sign = '\0';
  else //if (is_negative(i1.s) == false && is_negative(s))
    sign = '-';
  //else
    //sign = '-';

  while ((*tmp1) != "0") {

    // as long as its right digit is zero
    while ((*tmp1) != "0" && (*tmp1)[tmp1->length() - 1] == '0') {
      big_part.s += '0';
      tmp1->erase(tmp1->length() - 1); // removes one digit from the right side of tmp1, this digit is actually 0
    } // while

    counter = counter - sample;
    result = result + big_part; // will use addition for multiplication
  } // while

  if (sign == '-')
    result.s.insert(0, 1, '-');

  return result;
} // integer::operator*

integer integer::operator/(const integer &i1) const {
  // problem: you want to divide p = 123 by q = 11
  // solution: as long as q is smaller than p multiply q with 10 and save the result into tmp
  //           remember how many times you did the multiplication
  //           11 * 10 = 110 (just one time multiplication with 10 [10 times 11], add 10 to result)
  //           123 - 110 = 13
  //           13 - 11 = 2 (just one time 11, add 1 to result)
  //           result = 11

  integer sample1("1");
  static const integer sample2("10");

  integer result("0");

  integer temp1(s);
  integer temp2(i1);

  char sign = '\0';

  if (i1 == "0")
    throw operation_not_allowed_exception("Division by zero is not allowed!");

  if (is_negative(i1.s) && is_negative(s)) {
    temp1.s.assign(s, 1, s.length() - 1);
    temp2.s.assign(i1.s, 1, i1.s.length() - 1);
  } else if (is_negative(i1.s) == false && is_negative(s) == false) {
    // nothing to do
  } else if (is_negative(i1.s) == false && is_negative(s)) {
    sign = '-';
    temp1.s.assign(s, 1, s.length() - 1);
  } else {
    sign = '-';
    temp2.s.assign(i1.s, 1, i1.s.length() - 1);
  } // else

  while (temp1 >= temp2) {

    // speeds up the division-operation by multiplication
    while ((temp1.len() - 1) > temp2.len()) {
      sample1 = sample1 * sample2;
      temp2 = temp2 * sample2;
    } // while

    result = result + sample1;
    temp1 = temp1 - temp2;

    while (temp2 > temp1 && temp2 > i1.get_abs()) {
      temp2.s.erase(temp2.s.length() - 1); // cuts one digit from the right side of temp2
      sample1.s.erase(sample1.s.length() - 1); // cuts one digit from the right side of sample1
    } // while
  } // while

  if (sign == '-' && result.s != "0")
    result.s.insert(0, 1,  '-');

  if (temp1.s.length() == 0)
    result.rest = "0";
  else
    result.rest = temp1.s;

  return result;
} // integer::operator/

integer integer::operator%(const integer &i1) const {
  integer result = ((*this) / i1).rest;
  return result;
} // integer::operator%

integer integer::operator^(const integer &i1) const {
  // see operator*
  // version 1 simply multiplies (*this) or s with itself, i1 times

  // version 2 uses the following algorithm:
  // 0: take a temporary variable and name it "result", assign (*this) or s to the result
  // 1: convert i1 to its binary format
  // 2: ignore the most left digit of that binary number
  // 3: for each 0, calculate result ^ 2 and save it to result again
  // 4: for each 1, calculate (result ^ 2) * (*this) or s and save it to result again
  // 5: if there is no more binary digit left, then you will have the result

  // version 2 is in most cases faster than version 1, that is why we commented out the version 1
  // for a ^ n
  // version 2 needs 2 * log2(n) multiplications while version 1 needs n multiplications

  // version 1
  // integer result("1");

  // version 2
  integer result(s);

  long long to = converter::to_long_long(i1.s);

  if (i1 == "0") {
    // (x ^ 0) = 1 (for any x)
    result = "1";
    return result;
  } // if

  if (is_negative(i1.s))
    throw not_supported_exception("Negative numbers are not supported yet!");

  if (to > INT_MAX)
    throw operation_not_allowed_exception("Maximum supported number is: 2,147,483,647");

/*
  // version 1

  for (unsigned int i = 0; i < to; ++i)
    result = result * (*this);
*/

  // version 2

  //string binary = decimal_to_binary((unsigned int) to);
  // or
  // this one is more efficient
  const string binary = int_to_bin((unsigned int) to);

  // i starts from 1 and not from 0, we ignore the first binary digit here
  for (unsigned short i = 1; i < binary.length(); ++i) {
    if (binary[i] == '0')
      result = result * result;
    else
      result = (result * result) * (*this);

  } // for i

  return result;
} // integer::operator^

integer integer::get_abs() const {
  integer result;

  if (is_negative(s) == true)
    result.s.assign(s, 1, s.length() - 1);
  else
    result.s = s;

  return result;
} // integer::get_abs

integer::integer(const integer &i1) : s(i1.s), rest(i1.rest) {
 // nothing to do
} // integer::integer

integer::integer() : s(global_empty_string), rest("0") {
  // nothing to do
} // integer::integer

integer::integer(const string &s) : s(s), rest("0") {
  // nothing to do
} // integer::integer

integer::~integer() {
  // nothing to do
} // integer::~integer

ostream &operator<<(ostream &os, const integer &i1) {
  string str_cnv;

  os << converter::thousand_separator(i1.s, str_cnv);
  os << " Rest: " << i1.rest;
  return os;
} // operator<<
